/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.easy._69;

/**
 * 实现 int sqrt(int x) 函数。
 *
 * 计算并返回 x 的平方根，其中 x 是非负整数。
 *
 * 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
 *
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.easy._69
 * @ClassName: Sqrtx
 * @Author: linyaonan
 * @Date: 2019/10/22 16:49
 */
public class Sqrtx {

    public int mySqrt(int x) {
        if (x == 0 || x == 1) {
            return x;
        }
        int max = 46340;
        if (x <= 9) {
            Integer i = getInteger(x, x);
            if (i != null) {
                return i;
            }
        } else {
            // 二分法查找,int类型最大的值为 Integer.MAX_VALUE 平方根最大为46340
            int left = 3;
            int right = max + 1;
            int mid = (right - left) / 2 + left;
            while (left < right - 1) {
                if (mid*mid > x) {
                    right = mid;
                } else {
                    left = mid;
                }
                mid = (right - left) / 2 + left;
            }
            return mid;
        }
        return max;
    }

    private Integer getInteger(int x, int max) {
        for (int i = 1; i <= x; i++) {
            int p = i*i;
            if (p == max) {
                return i;
            }
            if (p > max) {
                return i - 1;
            }
        }
        return null;
    }
}
